package 力扣;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 示例 1:
 输入: nums = [1,1,1,2,2,3], k = 2
 输出: [1,2]
 示例 2:

 输入: nums = [1], k = 1
 输出: [1]

 */

public class _347前K个高频元素 {
    //思路:1.遍历nums,利用map.getOrDefault()key为num,value为num出现的次数
    //2.定义一个List数组长度nums.length+1因为可能会出现nums[]里面都是相同数字的情况,索引为出现的次数,值为integer[]因为可能有出        现次数相同的情况
    //3.遍历map,将num和num出现的次数存入到list中
    //4.遍历list从大到小
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ret = new ArrayList<Integer>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //
        List<Integer>[] list = new List[nums.length+1];
        for(int key:map.keySet()){

            int frequency = map.get(key);
            //如果该位置为空的话,创建
            if(list[frequency] ==null){
                list[frequency] = new ArrayList<Integer>();
            }
            //添加数据
            list[frequency].add(key);

        }
        //遍历list数组
        for(int i = list.length - 1; i >= 0 && ret.size() < k; i--) {
            if(list[i] != null) {
                ret.addAll(list[i]);
            }
        }
        return ret;


    }
}
